from numpy import *
from random import choice
import itertools
import sys

n = 50
rho = 0.4


def randgraph(n, rho):
    int_lb = 1
    int_ub = 10

    adj_mat = zeros( (n-1, n-1) )

    # Start from i to j+1
    up_tri_ind = [(i,j) for j in range(n-1) for i in range(j+1)]

    # Init the list of degrees at each node
    node_deg = [0] * n
    nodes = range(n)

    # Generate the node-node adjacent (n-1) * (n-1) matrix
    for ind in up_tri_ind:
        if random.uniform() < rho:
            adj_mat[ind] = random.randint( int_lb, int_ub )
            node_deg[ ind[0] ] += 1
            node_deg[ ind[1] + 1 ] += 1

    #print adj_mat
    #print node_deg
    # Check for node degrees and modify the adj_mtx
    for i in range( len(node_deg) ):
        if node_deg[i] == 0: #the node is isolated
            # Generate two new edges
            print "The graph is isolated try another one"
            sys.exit()
        elif node_deg[i] == 1: #the node is a leaf
            print "Dectect leaf node"
            nodes_rest = range(n)
            nodes_rest.remove(i)

            j = choice(nodes_rest)

            # Generate one new edges
            if i > j:
                adj_mat[ (j, i-1) ] = random.randint( int_lb, int_ub )

            else:
                adj_mat[ (i, j-1) ] = random.randint( int_lb, int_ub )

            # Update degrees at the nodes 
            node_deg[ i ] += 1
            node_deg[ j ] += 1

    #print adj_mat
    #print node_deg

    m = sum(node_deg) / 2.0

    #print "rho: ", rho
    #print "m/(n(n-1)/2): ", m / (n*(n-1)/2)

    return adj_mat
